package com.spirng.leetcode.day07;

public class Test235 {
    TreeNode left;
    TreeNode right;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }else if(right!=null&&left==null){
            return right;
        } else if (right==null&&left!=null) {
            return left;
        }
        return null;
    }
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root.val> q.val&&root.val> p.val){
           return   lowestCommonAncestor1(root.left,p,q);
        }
        if(root.val< q.val&&root.val<p.val){
            return  lowestCommonAncestor1(root.right,  p, q);
        }
          return root;

    }
}
